package leetcode.editor.cn.dsa27_mst;
//给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, we
//ighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权
//值和最小。 
//
// 请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在
//某些最小生成树中但不会出现在所有最小生成树中的边。 
//
// 请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。 
//
// 示例 1：
// 输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
//输出：[[0,1],[2,3,4,5]]
//解释：上图描述了给定图。
//下图是所有的最小生成树。
//
//注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
//边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。
//
// 示例 2 ： 
// 输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
//输出：[[],[0,1,2,3]]
//解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。
// 
//
// 提示： 
// 2 <= n <= 100
// 1 <= edges.length <= min(200, n * (n - 1) / 2) 
// edges[i].length == 3 
// 0 <= fromi < toi < n 
// 1 <= weighti <= 1000 
// 所有 (fromi, toi) 数对都是互不相同的。 
// 
// Related Topics 深度优先搜索 并查集 
// 👍 26 👎 0


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class FindEdgesInMST1489 {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private int[][] edgesCopy;
        private int[] parent;
        public void init(int n) {
            if (parent == null) {
                parent = new int[n];
            }
            for (int i = 0; i < n; i++) {
                // 每个顶点看作一个树（集合），根节点初始化为其自身
                parent[i] = i;
            }
        }

        public int find(int i) {
            while (parent[i] != i) {
                parent[i] = parent[parent[i]];
                i = parent[i];
            }
            return parent[i];
        }
        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) { // 不在一个集合，则合并
                parent[rootY] = rootX;
                return true;
            }
            return false;
        }

        public int kruskal(int[][] edges, int n, int index, boolean giveOrTake) {
            init(n); // 初始化并查集
            int mstWeightSum = 0, mstEdgeCount = 0;
            /* 伪关键边处理 */
            if (!giveOrTake && index != -1) {
                // 节点合并，计算权值和
                parent[edgesCopy[index][1]] = edgesCopy[index][0];
                mstWeightSum += edgesCopy[index][2];
                mstEdgeCount++;
            }
            // 遍历每条边，合并不在同一个树（集合）的节点
            for (int i = 0; i < edges.length && mstEdgeCount < n - 1; i++) {
                /* 关键边处理 */
                if (giveOrTake && edges[i] == edgesCopy[index]) {
                    continue; // 跳过
                }
                if(union(edges[i][0], edges[i][1])) {
                    // 合并成功则为最小生成树的一条边
                    mstWeightSum += edges[i][2];
                    mstEdgeCount++; // 优化：最小生成树中边的数量最多为n-1个
                }
            }
            // 可能会发生去掉关键边之后不连通的情况
            // 例如有4个顶点，其中ABC成环，A同时连接着D，如果去掉关键边AD
            // 则得到的关键边只有两条，虽然权值和更小，但是没有形成生成树
            if (mstEdgeCount == n - 1) {
                return mstWeightSum;
            }
            return Integer.MAX_VALUE;
        }

        public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
            edgesCopy = edges.clone();
            Arrays.sort(edges, (i1, i2) -> i1[2] - i2[2]); // 按照权重进行排序
            int minSum = kruskal(edges, n, -1, false);
            List<List<Integer>> result = new LinkedList<>();
            List<Integer> keyEdge = new ArrayList<>(edges.length); // 关键边
            List<Integer> pseudoKE = new ArrayList<>(edges.length); // 伪关键边
            result.add(keyEdge);
            result.add(pseudoKE);
            for (int i = 0; i < edges.length; ++i) {
                if (kruskal(edges, n, i, true) > minSum) {
                    // 去掉该边，权值和更大，说明是关键边
                    keyEdge.add(i);
                } else if (kruskal(edges, n, i, false) == minSum) {
                    // 非关键边的情况如果加入该边，权值和不变，说明是伪关键边
                    pseudoKE.add(i);
                }
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}